1. Field of the Invention
This invention relates to data storage.
2. Description of the Prior Art
A data storage medium such as a magnetic or magneto-optical disk medium generally has "header" information to define the location, current use and properties of data files stored on the disk. The header information may typically comprise one or more lengthy tables of entries, each entry relating to a particular logical file or section of the disk.
Similar lengthy tables of entries can occur in data storage applications such as computer databases.
In many cases, the table entries are set up in the order in which the data files are recorded on the disk, or in the case of the database example, the order in which the database entries are loaded into the database. However, when a file or database entry is subsequently deleted, it is often not worth the trouble to shuffle the entire table down to fill the free space vacated by the deleted entry. Thus, after a period of usage, there will tend to be free table entries throughout the table.
Unfortunately, however, searching for such free table entries would involve sequentially reading a good deal of the table every time a new entry is to be added to the table. This data processing and storage medium access overhead is not often worthwhile, and it is easier to add a new table entry to the end of the existing entries than to try to fit it into a vacated space earlier in the table.